package 力扣算法练习.main1.part1;

import java.util.ArrayList;
import java.util.List;

public class day20 {
    /*
    给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
    https://leetcode.cn/problems/spiral-matrix/
     */
    //旋转进行遍历,时间复杂度o(n*m)
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result=new ArrayList<>();
        int m=matrix.length,n=matrix[0].length;
        int sum=m*n;//总元素数
        int top=0,bottom=m-1,right=n-1,left=0;
        while(sum>0){
            //下面的for如果不加sum>0就会出现sum已经<=0了但后面的for循环还会执行list就会多增加元素
            for (int i =left; i <=right&&sum>0; i++) {
                result.add(matrix[top][i]);
                sum--;
            }
            top++;
            for (int i = top; i <= bottom&&sum>0; i++) {
                result.add(matrix[i][right]);
                sum--;
            }
            right--;
            for (int i =right ; i >=left&&sum>0 ; i--) {
                result.add(matrix[bottom][i]);
                sum--;
            }
            bottom--;
            for (int i = bottom; i>=top&&sum>0 ; i--) {
                result.add(matrix[i][left]);
                sum--;
            }
            left++;
        }
        return result;
    }



    /*
    给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
    数组中的每个元素代表你在该位置可以跳跃的最大长度。
    判断你是否能够到达最后一个下标
    https://leetcode.cn/problems/jump-game/
     */
    //官方解
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }

}
